package Algorithm.greedyAlgorithm;


/**
 * 670. 最大交换 https://leetcode.cn/problems/maximum-swap/
 * 题目简述：给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
 */
public class MaximumSwap {

    public static void main(String[] args) {
        new MaximumSwap().maximumSwap(2736);
    }
    /**
     * 思路：从较低位找出最大值，与不等于这个最大值的最高位交换。从右向左扫描，使用一个数组保存[i,n-1]前缀中的最大值并且最远的索引
     * 最后从左向右扫描，找到第一个前缀最大值不是自己的数，然后与最大值进行交换
     */
    public int maximumSwap(int num) {
        char[] arr = Integer.toString(num).toCharArray();
        int n = arr.length;
        int[] preMaxIndex = new int[n];
        preMaxIndex[n-1] = n-1; //n-1前缀中最大值索引就是自己
        for (int i = n-2;i >= 0;i--) { //从右向左扫描
            if (arr[i] <= arr[preMaxIndex[i+1]]) //当当前值小于等于前缀中最大值时，更新索引，等于也要更新，因为需要的是最远处的最大值
                preMaxIndex[i] = preMaxIndex[i+1];
            else preMaxIndex[i] = i; //否则最大值索引为自己
        }
        for (int i = 0;i < n;i++) { //最后从左向右扫描，找到第一个前缀最大值不是自己的数，然后与最大值进行交换
            if (arr[i] != arr[preMaxIndex[i]]) { //要根据值判断，不能根据索引判断，因为可能值一样但是i != preMaxIndex[i]
                char t = arr[i];
                arr[i] = arr[preMaxIndex[i]];
                arr[preMaxIndex[i]] = t;
                break;
            }
        }
        return Integer.parseInt(new String(arr));
    }
}
